BOJ_12738_가장 긴 증가하는 부분 수열3

LIS(Longest Increasing Subsequence) 알고리즘 중 이분탐색을 활용하는 문제

수열의 길이가 1,000,000이므로 dp를 써서 O(N^2)으로 풀면 시간 초과가 난다
그렇기에 이분탐색으로 O(NlogN)으로 풀어야 한다

BOJ_12015_가장 긴 증가하는 부분 수열2와의 차이는
 수열 A가 -1,000,000,000 ≤ Ai ≤ 1,000,000,000 의 범위를 갖는다는 것이다
그러나 java에서 Integer.MAX_VALUE = 2,147,483,647이므로 코드에는 딱히 영향이 없기에 동일한 풀이로 풀면 된다

package solve.BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class BJO_12738_가장_긴_증가하는_부분_수열2 {  
    public static void main(String[] args) throws IOException {  
        // 입력  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int N = Integer.parseInt(br.readLine());  
  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int[] nums = new int[N];  
        for (int i = 0; i < N; i++) {  
            nums[i] = Integer.parseInt(st.nextToken());  
        }  
  
        // 이분탐색  
        // 수열의 길이가 백만이므로 dp 대신 이분탐색 사용  
        int[] lis = new int[N];  
        int length = 0;  
        for (int i = 0; i < N; i++) {  
            int num = nums[i];  
            int pos = binarySearch(num, 0, length, lis);  
            lis[pos] = num;  
  
            if (pos == length) length++;  
        }  
  
        System.out.println(length);  
    }  
  
    public static int binarySearch(int num, int start, int end, int[] lis) {  
        while (start < end) {  
            int mid = start + (end - start) / 2;  
  
            if (lis[mid] < num) start = mid + 1;  
            else end = mid;  
        }  
  
        return end;  
    }  
}